package codingforgreat.class22;


import codingforgreat.class05.Hash;

import java.util.HashMap;

//lc 956
public class Class05_TallestBillboard {

    public int tallestBillboard(int[] rods) {
        HashMap<Integer,Integer> dp = new HashMap<>(),cur;
        dp.put(0,0);
        for(int num : rods){
            if(num != 0){
                cur = new HashMap<>(dp);
                for(int d : cur.keySet()){
                    int diffMore = cur.get(d); // 最好的一对，较小集合的累加和
                    // x决定放入，比较大的那个
                    dp.put(d + num, Math.max(diffMore, dp.getOrDefault(num + d, 0)));
                    // x决定放入，比较小的那个
                    // 新的差值 Math.abs(x - d)
                    // 之前差值为Math.abs(x - d)，的那一对，就要和这一对，决策一下
                    // 之前那一对，较小集合的累加和diffXD
                    int diffXD = dp.getOrDefault(Math.abs(num - d), 0);
                    if (d >= num) { // x决定放入比较小的那个, 但是放入之后，没有超过这一对较大的那个
                        dp.put(d - num, Math.max(diffMore + num, diffXD));
                    } else { // x决定放入比较小的那个, 但是放入之后，没有超过这一对较大的那个
                        dp.put(num - d, Math.max(diffMore + d, diffXD));
                    }
                }
            }
        }
        return dp.get(0);
    }
}
